#!/usr/bin/env python
# encoding: utf-8
"""
untitled.py

Created by Samrach Nouv on 2010-04-01.
Copyright (c) 2010 __MyCompanyName__. All rights reserved.
"""

import sys
import os
import re

#Part 1.a
def isPalindrome(s):
	mid = len(s)/2
	skip = len(s)%2 #skip the middle character in case the length is odd
	p1 = s[:mid]
	p2 = s[mid+skip:]
	p2_reversed = p2[::-1]
	if p1 == p2_reversed:
		return True
	return False
	
#Part 1.b recursive functions
def choose(n, k):
	if n==k or k==0: 
		return 1
	else:
		return choose(n-1,k-1) + choose(n-1, k)
		
#Part 1.c lists
def combinations(s, k):
	#print 'should be'
	#print choose(len(s),k)
	temp = []
	combinations_helper(temp,[],s, k)
	return temp
	
def combinations_helper(result, temp, s, k):
	if k==1:
		for e in s:
			t = temp[:]
			t.append(e)
			result.append(t)
	else:
		i = 0
		while(len(s[i+1:]) >= k-1):
			base = s[i]
			t=temp[:]
			t.append(base)
			combinations_helper(result, t, s[i+1:], k-1)
			i=i+1

#part 1.d hashes
def countWords(s):
	tokens = s.split()
	d = dict()
	for token in tokens:
		if (token in d):
			d[token]=d[token]+1
		else:
			d[token]=1
	result = []
	for key in d.keys():
		result.append([key,d[key]])
	return result

#part 1.e regular expressions 
def generalizeNumbers(s):
	return re.sub ( '\d+', '(some number)', s )
	
def main():
	print ''
	print '------------Part1.a------------'
	print ''
	print 'Is "MADAMIMADAM" a palindrome ?'
	print isPalindrome('MADAMIMADAM')
	print 'Is "Not a palindrome" a palindrome ?'
	print isPalindrome('Not a palindrome')
	print ''
	print '------------Part1.b------------'
	print ''
	print 'choose(5, 3) = %d' % choose(5, 3)
	print 'choose(3, 3) = %d' % choose(3, 3)
	print 'choose(3, 1) = %d' % choose(3, 1)
	print 'choose(10, 7) = %d' % choose(10, 7)
	print ''
	print '------------Part1.c------------'
	print ''
	print combinations(['H', 'Li', 'Na', 'K', 'Rb'], 3)
	print ''
	print '------------Part1.d------------'
	print ''
	print countWords("Let's compare red apples and green apples")
	print ''
	print '------------Part1.e------------'
	print ''
	print generalizeNumbers("I drank 3 lattes and 12 ounces of water.")
	print generalizeNumbers("I have 3 cars, 12 boxes of chocolate, and 3 cans of soda.")
	print ''
	pass




if __name__ == '__main__':
	main()

